9018. n-th integer divisible by a or b
Given two
integers a and
b. Find the n-th positive integer that is divisible by either a or b.
Input. Three integers a, b and n (a, b, n ≤ 109).
Output. Print the n-th positive integer divisible by
either a or b. It is known that the answer is no
more than 109.
|
Sample
input 1 |
Sample
output 1 |
|
2 5 10 |
16 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
3 7 25 |
57 |
SOLUTION
binary search
Algorithm analysis
Let function f(n) computes the
number of positive integers in the interval [1; n], divisible by either a or b. This
number is
n / a + n
/ b – n / LCM(a, b)
Let x
be the n-th number. Then x must be the smallest positive integer
such that f(x) = n. We will search for it with a binary
search, starting from the segment [left;
right] = [1; 109]. Let mid = (left + right) / 2. If f(mid) ≥ n, then the search should be continued on the segment [left; mid], otherwise on the segment [mid
+ 1; right].
Example
Consider the first sample, where a = 2, b = 5. It is
necessary to find the smallest x for
which f(x) = 10. Let's calculate some
values:
·
f(15)
= 15 / 2 + 15 / 5 – 15 / 10 = 7 + 3 – 1 = 9;
·
f(16)
= 16 / 2 + 16 / 5 – 16 / 10 = 8 + 3 – 1 = 10;
·
f(17)
= 17 / 2 + 17 / 5 – 17 / 10 = 8 + 3 – 1 = 10;
·
f(18)
= 18 / 2 + 18 / 5 – 18 / 10 = 9 + 3 – 1 = 11;
The smallest solution to the equation f(x)
= 10 is x = 16.
Algorithm realization
Next functions compute GCD and LCM.
long long gcd(long long a, long long b)
{
return (b == 0) ? a : gcd(b, a % b);
}
long long lcm(long long a, long long b)
{
return a /
gcd(a, b) * b;
}
Function f(n) returns the number of positive
integers not greater than n, divisible by either a or b.
long long f(long long n)
{
return n / a
+ n / b - n / lcm(a, b);
}
Read the input data.
scanf("%lld %lld %lld",
&a, &b, &n);
Start the binary search. We are looking for the smallest value left for which f(left)
= n.
left = 1; right = 1e9;
while (left < right)
{
middle
= (left + right) / 2;
if
(f(middle) >= n)
right
= middle;
else
left
= middle + 1;
}
Print the answer.
printf("%lld\n",
left);
Java realization
import java.util.*;
import java.io.*;
public class Main
{
static long gcd(long a, long b)
{
return (b ==
0) ? a : gcd(b, a % b);
}
static long lcm(long a, long b)
{
return a / gcd(a, b) * b;
}
static long f(long n, long a, long b)
{
return n / a + n / b - n / lcm(a, b);
}
public static void
main(String[] args)
{
FastScanner con = new
FastScanner(new InputStreamReader(System.in));
long a = con.nextInt();
long b = con.nextInt();
long n = con.nextInt();
long left = 1,
right = 1000000000;
while (left <
right)
{
long middle = (left + right) /
2;
if (f(middle, a, b)
>= n)
right = middle;
else
left = middle + 1;
}
System.out.println(left);
}
}
class FastScanner
{
private BufferedReader br;
private StringTokenizer st;
public
FastScanner(InputStreamReader reader)
{
br = new BufferedReader(reader);
}
public
String next()
{
while (st == null || !st.hasMoreTokens())
{
try
{
st = new StringTokenizer(br.readLine());
} catch
(Exception e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return Integer.parseInt(next());
}
public void
close() throws Exception
{
br.close();
}
}